/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package progentiere.knapsackprb;

import java.util.ArrayList;
import java.util.Collections;


public class CoreDP extends Algorithm
{
    static int CRITICALNOTFOUND = -1;
    
    @Override
    Solution solve(KnapSackProblem problem) 
    {
        Solution incSol = new Solution(problem.getNbItems()); // local best solution
        
        Collections.sort(problem.getItems());
        
        int c = findCriticalItem(problem);
        
        if(c == CRITICALNOTFOUND)
        {
            System.err.print("NIQUE SA RACE SALE BATARD");
            for(int i = 0 ; i < problem.getNbItems() ; i++)
            {
                incSol.getContent()[i] = 1;
            }
        }
        else // = no critical item, sum(w_i) <= W 
        {
            int a = c;
            int b = c - 1;
            int n = problem.getNbItems() - 1;

            ArrayList<DPCoreLabel> labels = new ArrayList<>();
            ArrayList<DPCoreLabel> labelsPrim = new ArrayList<>();
            double wBar = 0.0;
            double pBar = 0.0;

            for (int i = 0 ; i < c ; i++)
            {
                wBar += problem.getItems().get(i).getWeight();
                pBar += problem.getItems().get(i).getProfit();
                incSol.getContent()[i] = 1;
            }
            
            DPCoreLabel initLabel = new DPCoreLabel(c, c-1, wBar, pBar, incSol);
            
            labels.add(initLabel);
                
                System.out.println("w " + incSol.getWeight(problem) + " | p "+ incSol.getProfit(problem) + " " +incSol);
            while(a > 0 || b < n)
            {
                            System.out.println("a : " + a + "; b : " + b + "; labels : " + labels.size());  
                            System.out.println(incSol);  
                            
                if(b < n)
                {
                    labelsPrim.clear();
                    b++;
                    for(DPCoreLabel label : labels)
                    {
                        DPCoreLabel labelNewB0 = new DPCoreLabel(
                                a, 
                                b, 
                                label.getwBar(), 
                                label.getwTilde(),
                                label.getpBar(), 
                                label.getpTilde(),
                                label.getX()
                        ); 
                        //System.out.println(labelNewB0.getX());
                        labelNewB0.getX().getContent()[b] = 0;
                        //System.out.println(labelNewB0.getX() + "\n");
                        // check dominance
                        boolean isDominated = false;
                        for(int i = 0 ; i < labelsPrim.size() ; i++)
                        {
                            if(labelsPrim.get(i).dominates(labelNewB0))
                            {
                                isDominated = true;
                                break;
                            }
                            if(labelNewB0.dominates(labelsPrim.get(i)))
                            {
                                labelsPrim.remove(i);
                            }
                        }
                        
                        if(labelNewB0.getW() <= problem.getCapacity()
                            && !labelNewB0.isRelaxLesserThanInc(problem, incSol.getProfit(problem)) 
                            && !isDominated
                          )
                        {
                            labelsPrim.add(labelNewB0);
                        }
                        
                        if(label.getwTilde() + problem.getItems().get(b).getWeight() <= problem.getCapacity())
                        {
                            DPCoreLabel labelNewB1 = new DPCoreLabel(
                                a, 
                                b, 
                                label.getwBar(), 
                                label.getwTilde() + problem.getItems().get(b).getWeight(),
                                label.getpBar(), 
                                label.getpTilde()+ problem.getItems().get(b).getProfit(),
                                label.getX()
                            );
                            labelNewB1.getX().getContent()[b] = 1;
                            // check dominance
                            for(int i = 0 ; i < labelsPrim.size() ; i++)
                            {                                
                                if(labelsPrim.get(i).dominates(labelNewB1))
                                {
                                    isDominated = true;
                                    break;
                                }
                                if(labelNewB1.dominates(labelsPrim.get(i)))
                                {
                                    labelsPrim.remove(i);
                                }
                            }

                            if(labelNewB1.getW() <= problem.getCapacity()
                                && !labelNewB1.isRelaxLesserThanInc(problem, incSol.getProfit(problem)) 
                                && !isDominated
                              )
                            {
                                labelsPrim.add(labelNewB1);
                            }
                        }
                        
                    }                    
                } // end if (b < n)

                //////////////////////labels.clear();
                if(a > 0)
                {
                    labelsPrim.clear();
                    a--;
                    for(DPCoreLabel label : labels)
                    {                    
                        DPCoreLabel labelNewA1 = new DPCoreLabel(
                                a, 
                                b, 
                                label.getwBar(), 
                                label.getwTilde(),
                                label.getpBar(), 
                                label.getpTilde(),
                                label.getX()
                        );
                        labelNewA1.getX().getContent()[a] = 1;
                        boolean isDominated = false;
                        for(int i = 0 ; i < labelsPrim.size() ; i++)
                        {
                            if(labelsPrim.get(i).dominates(labelNewA1))
                            {
                                isDominated = true;
                                break;
                            }
                            if(labelNewA1.dominates(labelsPrim.get(i)))
                            {
                                labelsPrim.remove(i);
                            }
                        }
                        
                        if(labelNewA1.getW() <= problem.getCapacity()
                            && !labelNewA1.isRelaxLesserThanInc(problem, incSol.getProfit(problem)) 
                            && !isDominated
                          )
                        {
                            labelsPrim.add(labelNewA1);
                        }
                                                
                        DPCoreLabel labelNewA0 = new DPCoreLabel(
                                a, 
                                b, 
                                label.getwBar() - problem.getItems().get(a).getWeight(), 
                                label.getwTilde(),
                                label.getpBar() - problem.getItems().get(a).getProfit(), 
                                label.getpTilde(),
                                label.getX()
                        );
                        
                        labelNewA0.getX().getContent()[a] = 0;
                        
                        isDominated = false;
                        for(int i = 0 ; i < labelsPrim.size() ; i++)
                        {
                            if(labelsPrim.get(i).dominates(labelNewA0))
                            {
                                isDominated = true;
                                break;
                            }
                            if(labelNewA0.dominates(labelsPrim.get(i)))
                            {
                                labelsPrim.remove(i);
                            }
                        }
                        
                        if(labelNewA0.getW() <= problem.getCapacity()
                            && !labelNewA0.isRelaxLesserThanInc(problem, incSol.getProfit(problem)) 
                            && !isDominated
                          )
                        {
                            labelsPrim.add(labelNewA0);
                        }
                    }
                    
                } // end if (a > 0)
                
                labels.clear();
                for(DPCoreLabel labelPrim : labelsPrim)
                {
                    if(labelPrim.getP() > incSol.getProfit(problem))
                    {
                        incSol = new Solution(labelPrim.getX());
                    }
                    labels.add(labelPrim);
                }
                //System.out.println("w " + incSol.getWeight(problem) + " | p "+ incSol.getProfit(problem) + " " +incSol);
            } // end while(a > 0 || b < n)            
        }
                System.out.println("w " + incSol.getWeight(problem) + " | p "+ incSol.getProfit(problem) + " " +incSol);
        
        incSol.setOptimal();
        return incSol;
    }

    private int findCriticalItem(KnapSackProblem problem)
    {
        Collections.sort(problem.getItems());
        
        double remainingCapacity = problem.getCapacity();
        
        for(int i = 0 ; i < problem.getNbItems() ; i++)
        {
            if(problem.getItems().get(i).getWeight() <= remainingCapacity)
            {
                remainingCapacity -= problem.getItems().get(i).getWeight();
            }
            else 
            {
                return i;
            }
        }
        
        return CRITICALNOTFOUND;
    }
    
}
